//
// Created by LiuYou on 2021/12/2.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>


static int randomNumberFromTheRange(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


/*
 * 某个数在 index位置, 能否往下移动。
 * index: 我是从哪个位置往下做 heapify(); 可以从根结点也可以从任意的一个结点。
 * heapSize: 这个参数管着左右孩子是否越界。
 */
static void heapify(std::vector<int>& arr, int index, int heapSize) {
    // 左孩子的下标。
    int left = index * 2 + 1;
    // 下方还有孩子的时候。
    //
    // 左孩子有没有越界。
    // left < heapSize 表示 index结点 是否还有孩子结点, 如果左孩子结点都没有,
    // 那么一定没有右孩子结点, 因为右孩子结点下标位置为 2 * index + 2。
    while (left < heapSize) {
        // 1.
        // 两个孩子中, 谁的值大, 把下标给 largest。
        //
        // left + 1 是右孩子的下标, left + 1 < heapSize 这句表达式表示
        // 如果有右孩子, 并且 右孩子的值还大于左孩子的值。
        // 那么 largest 就是右孩子的下标。
        // 即两个孩子中谁的值更大, 把谁的下标给 largest。
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ?
                      left + 1 : left;
        // 2.
        // 父结点和孩子结点之间, 谁的值大, 把下标给 largest。
        largest = arr[largest] > arr[index] ? largest : index;

        // 如果没有孩子比当前的结点的值大, 那就不用往下走了, 已经是一个大顶堆了。
        if (largest == index) {
            break;
        }

        // 如果有一个孩子的值比当前结点的值大, 那么就将孩子的值与当前结点的值做交换。
        std::swap( arr[largest], arr[index] );
        // 然后 index往下走。将刚刚交换的大的孩子结点的下标位置赋值给 index。
        index = largest;
        // 然后新的 要判断的结点是当前的 这个结点的左孩子结点。
        left = index * 2 + 1;
    }
}


/*
 * 某个数现在处在 index 位置, 往上继续移动。
 *
 * 某个数在 index位置, 维持一个大顶堆, 需要把这个数放到一个合适的位置上。
 */
static void heapInsert(std::vector<int>& arr, int index) {
    /*
     * 如果我当前的结点的值, > 父结点的值, ...
     *
     * 那么这个 while什么时候停?
     * 某一个结点不再比这个结点的父结点大了, 那么就停了。
     *
     * 如果 index是 0, 那么 (0 - 1) / 2 = 0, 那么这个 arr[0] > arr[0]
     * while循环条件不会成立, 即大顶堆调整完毕。
     */
    while (arr[index] > arr[(index - 1) / 2]) {
        // ..., 那么 与父结点的值做交换。
        std::swap( arr[index], arr[(index - 1) / 2] );
        // 交换了之后, index来到交换的位置。
        index = (index - 1) / 2;
    }
}


static void heapSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    // 执行完这个 for循环后, 就构建了一个大顶堆。
    for (int i = 0; i < arr.size(); ++i) {
        heapInsert( arr, i );
    }

    // 下面进行堆排序。
    int heapSize = arr.size();
    std::swap( arr[0], arr[--heapSize] );
    while (heapSize > 0) {
        heapify( arr, 0, heapSize );
        std::swap( arr[0], arr[--heapSize] );
    }

}


int main(int argc, char** argv) {
    std::vector<int> arr( 10 );
    for (auto& item: arr) {
        item = randomNumberFromTheRange( 0, 100 );
    }

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;

    heapSort( arr );

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;


    return 0;
}
